Thread: Finding common values in the rows of a vector [Need Help]

Can somebody give me a hand with this? I'm doing this for a an application that would print of LCM and GCD (lowest common factor and greatest common divisor) with steps.

I need to get the common factors so I can highlight them when I'm printing them under factors. I tried googling but I could only find programs that would directly find LCM or GCD. It's important I have all the factors.

The best I could come up with:

Code:

int main() {
    vector <float> operands = { 9, 9, 4 };
    vector < vector <float> > factors;
    vector < vector <float> > factors_temp;
    vector <float> common_factors;

    for (const auto& x : operands)
        factors.push_back(prime_factors(x)); // returns a vector 
    
    factors_temp = factors;

    for (unsigned int i = 0; i < factors_temp.size(); i++) {
        for (unsigned int j = 0; j < factors_temp[i].size(); j++) {

            for (unsigned int k = 0; k < factors_temp.size(); k++) {
                for (unsigned int l = 0; l < factors_temp[k].size(); l++) {
                    if (k == i)
                        continue;

                    if (factors_temp[i][j] == factors_temp[k][l]) {
                        common_factors.push_back(factors_temp[i][j]);
                        factors_temp[i].erase(factors_temp[i].begin() + j);
                        factors_temp[k].erase(factors_temp[k].begin() + l);
                    }
                }
            }
        }
    }

    for (const auto& x : common_factors)
        cout << x << "\t";

    cin.get();
    return 0;
}

The logic is completely faulty though. It occasionally works for two operands.

Oh and also I need to erase common factors from the rows and columns themselves. (So they won't repeat while printing out, unless there is a better logic to this)

Thanks for reading, cheers!


here's the other part of the code:

Code:

#include <iostream>
#include <vector>
#include <string>
#include <Windows.h>

using namespace std;

void SetColor(int ForgC) // source: https://stackoverflow.com/questions/29574849/how-to-change-text-color-and-console-color-in-codeblocks
{
    WORD wColor;

    HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
    CONSOLE_SCREEN_BUFFER_INFO csbi;

    //We use csbi for the wAttributes word.
    if (GetConsoleScreenBufferInfo(hStdOut, &csbi))
    {
        //Mask out all but the background attribute, and add in the forgournd     color
        wColor = (csbi.wAttributes & 0xF0) + (ForgC & 0x0F);
        SetConsoleTextAttribute(hStdOut, wColor);
    }
    return;
}

vector <int> prime_factors(int number) {  // over-loaded function
    vector <int> prime_factors = { 1 };

    for (int i = 2; i <= number; i++) {
        while (number % i == 0) {
            number /= i;
            prime_factors.push_back(i);
        }
    }
    return prime_factors;
}

The reason I'm using a nested vector is to support any number of operands (I don't know a different way)

What should happen:
1) Any number of operands 1 to n must be allowed to be given as input
2) Given elements' factors are found and put as a unique row in 2D vector 'factors' (works) [idk if 2D vector is the way to go]
3) Elements common in all the rows are deleted in 'factors_temp' (faulty in my script)
4) Deleted elements that were common are added to new vector called 'common_factors' (faulty in my script)

(I think my script works for 2 operands)
If there is more than 2 it says vector out of range

You actually just want the factors of the gcd of the input values. So how about:

Code:

#include <iostream>
#include <vector>
 
int gcd(int a, int b) {
    return a == 0 ? b : gcd(b % a, a);
}
 
int gcda(const int *a, int n) {
    int d = a[0];
    for (int i = 1; i < n; i++)
        d = gcd(a[i], d);
    return d;
}
 
auto factors(int n) {
    std::vector<int> f;
    if (n > 1) {
        while (n % 2 == 0) {
            f.push_back(2);
            n /= 2;
        }
        for (int i = 3; n != 1; i += 2)
            while (n % i == 0) {
                f.push_back(i);
                n /= i;
            }
    }
    return f;
}
 
int main() {
    int a[4] = { 3*7, 2*3*5*7, 2*2*3*7, 3*3*7*7 };
    auto f = factors(gcda(a, 4));
    for (auto x: f)
        std::cout << x << ' ';
    std::cout << '\n';
}

BTW, 1 isn't really a prime factor. And you want to use integers, not floating point, although you might want to use long or long long.

Originally Posted by john.c

You actually just want the factors of the gcd of the input values. So how about:

Code:

#include <iostream>
#include <vector>
 
int gcd(int a, int b) {
    return a == 0 ? b : gcd(b % a, a);
}
 
int gcda(const int *a, int n) {
    int d = a[0];
    for (int i = 1; i < n; i++)
        d = gcd(a[i], d);
    return d;
}
 
auto factors(int n) {
    std::vector<int> f;
    if (n > 1) {
        while (n % 2 == 0) {
            f.push_back(2);
            n /= 2;
        }
        for (int i = 3; n != 1; i += 2)
            while (n % i == 0) {
                f.push_back(i);
                n /= i;
            }
    }
    return f;
}
 
int main() {
    int a[4] = { 3*7, 2*3*5*7, 2*2*3*7, 3*3*7*7 };
    auto f = factors(gcda(a, 4));
    for (auto x: f)
        std::cout << x << ' ';
    std::cout << '\n';
}

BTW, 1 isn't really a prime factor. And you want to use integers, not floating point, although you might want to use long or long long.

Dude I really appreciate it that you took the time to write that!
But umgh I need the common factors too.. hehe. So how would I do that?

Oh and float is because I plan to support finding GCD and LCM for floating values as well. And yea I might need to use long float, thanks!

(OH WAIT, I just realized.. prime factors of the GCD would be the common factors of the terms right..!)

phew thanks a lot.

There is no long float. Instead it's called double. But there's also long double.
For ints there's long and long long.

And I've never heard of a GCD of non-integers. Can you give an example?